package b_中等;

import leetcode.editor.cn.level.中等;
import 分类.二分查找;

import java.util.*;

/**
 * 给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。
 * <p>
 * 字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
 * <p>
 * 例如， “ace” 是 “abcde” 的子序列。
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "abcde", words = ["a","bb","acd","ace"]
 * 输出: 3
 * 解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
 * Example 2:
 * <p>
 * 输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
 * 输出: 2
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/number-of-matching-subsequences
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2023/4/24 10:11
 */
public class _792_匹配子序列的单词数 implements 中等, 二分查找 {

    public static void main(String[] args) {
        _792_匹配子序列的单词数 a = new _792_匹配子序列的单词数();
        int abcde = a.numMatchingSubseq("abcde", new String[]{  "bb"});
        System.out.println(abcde);
    }

    public int numMatchingSubseq(String s, String[] words) {
        // 对s进行预处理，保存每个字符出现的下标
        Map<Character, List<Integer>> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            List<Integer> orDefault = map.getOrDefault(s.charAt(i), new ArrayList<>());
            orDefault.add(i);
            map.put(s.charAt(i), orDefault);
        }
        // 遍历words数组 对每个元素的字符进行遍历然后进行二分查找

        int count = 0;
        for (String word : words) {
            boolean check = check(word, map);
            if (check) {
                count++;
            }

        }


        return count;
    }

    private boolean check(String word, Map<Character, List<Integer>> map) {
        // index为目标字符串当前的下标
        int index = 0;
        int i = 0;
        for ( ; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!map.containsKey(c)) {
                return false;
            }
            List<Integer> indexList = map.get(c);
            int extracted = extracted(index, indexList);
            if (extracted == -1) {
                return false;
            }
            index = extracted + 1;
        }
        return true;
    }

    private static int extracted(int target, List<Integer> indexList) {
        // 在indexList中找到第一个大于index的下标
        int left = 0, right = indexList.size();

        while (left < right) {
            int mid = left + (right - left) / 2;
            // 目标值在中间下标的右边
            if (indexList.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left == indexList.size()) {
            return -1;
        }
        return indexList.get(left) ;
    }
}
